#!/usr/bin/python3.5

# -*- coding: utf-8 -*-

#!/usr/bin/python3.5

# -*- coding: utf-8 -*-


def shellSort(arr):

    n = len(arr)//2
    while n>=1:
        for i in range(n):
            for j in range(i + n, len(arr), n):
                while j >= n and arr[j] < arr[j - n]:
                    arr[j-n], arr[j] = arr[j], arr[j-n]
                    j-=n

        n=n//2

    return arr





if __name__ =="__main__":

    a = [2, 8, 4, 5, 9, 4, 42, 0, 3, 6, 8]
    print(shellSort(a))
